/*
* leetcode 2516 每种字符至少取K个
* 
给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。
每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。
你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。

示例 1：
输入：s = "aabaaaacaabc", k = 2
输出：8
解释：
从 s 的左侧取三个字符，现在共取到两个字符 'a' 、一个字符 'b' 。
从 s 的右侧取五个字符，现在共取到四个字符 'a' 、两个字符 'b' 和两个字符 'c' 。
共需要 3 + 5 = 8 分钟。
可以证明需要的最少分钟数是 8 。
示例 2：

输入：s = "a", k = 1
输出：-1
解释：无法取到一个字符 'b' 或者 'c'，所以返回 -1 。
* */
/*
* 思路：将从两边取数转化为从中间取数
* */
class Solution {
    public int takeCharacters(String s, int k) {
        int n=s.length();
        char[] cs=s.toCharArray();
        int[] arr={-k,-k,-k}; //维护中间区间内各字母的最大数量
        for(char c:cs)arr[c-'a']++;
        if(arr[0]<0||arr[1]<0||arr[2]<0)return -1;
        if(arr[0]==0&&arr[1]==0&&arr[2]==0)return n;
        int left=0,right=0,max=0;
        while(right<n){
            arr[cs[right++]-'a']--;
            if(arr[0]<0||arr[1]<0||arr[2]<0){
                arr[cs[left++]-'a']++;
            }else{
                max=right-left>max?right-left:max;
            }

        }
        return n-max;
    }
}